function mergeSort(arr) {
  const len = arr.length
  if (len <= 1) return arr // 递归的边界
  const mid = Math.floor(len / 2) // 计算分割点
  const leftArr = mergeSort(arr.slice(0, mid)) // 递归分割左子数组
  const rightArr = mergeSort(arr.slice(mid, len)) // 递归分割右子数组
  return mergeArr(leftArr, rightArr) // 合并左右子树
}
// 合并两个数组
function mergeArr(arr1, arr2) {
  const len1 = arr1.length
  const len2 = arr2.length
  let i = 0,
    j = 0
  const res = []
  while (i < len1 && j < len2) {
    if (arr1[j] < arr2[j]) {
      res.push(arr1[i])
      i++
    } else {
      res.push(arr2[j])
      j++
    }
  }
  if (i < len1) {
    return res.concat(arr1.slice(i))
  } else {
    return res.concat(arr2.slice(j))
  }
}
const testArr = [9, 8, 7, 6, 5]
let res = mergeSort(testArr)
console.log(res)
